/// @tags: DP ConvexHullOptimization
#include <algorithm>
#include <cstdio>
#include <iostream>

using namespace std;

namespace BlueQuantum {

typedef long long LL;

int constexpr N = 3e5 + 5;
LL constexpr INF = 0x3f3f3f3f3f3f3f3f;

int n, m;
int stk[N];
LL t[N], sum[N];
LL f[N], g[N], *dp, h[N];

inline double X(int j) { return j; }

inline double Y(int j) { return dp[j] + ((LL)j * j - j) / 2 + sum[j]; }

inline double slope(int i, int j) { return (Y(i) - Y(j)) / (X(i) - X(j)); }

inline LL calc(int i, int j) {
  return dp[j] + ((LL)(i - j + 1) * (i - j)) / 2 - (sum[i] - sum[j]);
}

inline void DP() {
  for (int i = 1; i <= n; ++i) sum[i] = sum[i - 1] + t[i];
  int top = 1;
  stk[top] = 0;
  for (int i = 1; i <= n; ++i) {
    while (top > 1 && calc(i, stk[top]) <= calc(i, stk[top - 1])) top--;
    dp[i] = max(calc(i, stk[top]), dp[i - 1]);
    while (top > 1 && slope(stk[top - 1], i) >= slope(stk[top], stk[top - 1])) top--;
    stk[++top] = i;
  }
}

inline double X1(int j) { return j; }

inline double Y1(int j) { return f[j] + sum[j] + ((LL)j * j - j) / 2; }

inline double slope1(int i, int j) { return (Y1(i) - Y1(j)) / (X1(i) - X1(j)); }

inline LL calc1(int i, int j) {
  return g[i + 1] + ((LL)(i - j) * (i - j + 1)) / 2 - (sum[i] - sum[j]) + f[j];
}

inline double X2(int j) { return j; }

inline double Y2(int j) { return g[j + 1] + ((LL)j * j + j) / 2 - sum[j]; }

inline double slope2(int i, int j) { return (Y2(i) - Y2(j)) / (X2(i) - X2(j)); }

inline LL calc2(int i, int j) {
  return f[i] + ((LL)(j - i) * (j - i + 1)) / 2 - (sum[j] - sum[i]) + g[j + 1];
}

void solve(int l, int r) {
  if (l == r) return h[l] = f[l - 1] + g[l + 1] + 1 - t[l], void();
  int mid = (l + r) >> 1;
  solve(l, mid);
  solve(mid + 1, r);
  int top = 0;
  for (int i = l - 1; i < mid; ++i) {
    while (top > 1 && slope1(i, stk[top - 1]) >= slope1(stk[top], stk[top - 1])) top--;
    stk[++top] = i;
  }
  int head = 1;
  LL maxx = -INF;
  for (int i = r; i > mid; i--) {
    while (head < top && calc1(i, stk[head]) <= calc1(i, stk[head + 1])) head++;
    maxx = max(maxx, calc1(i, stk[head]));
    h[i] = max(h[i], maxx);
  }
  top = 0;
  for (int i = mid + 1; i <= r; ++i) {
    while (top > 1 && slope2(i, stk[top - 1]) >= slope2(stk[top], stk[top - 1])) top--;
    stk[++top] = i;
  }
  maxx = -INF;
  for (int i = l - 1; i < mid; ++i) {
    while (top > 1 && calc2(i, stk[top]) <= calc2(i, stk[top - 1])) top--;
    maxx = max(maxx, calc2(i, stk[top]));
    h[i + 1] = max(h[i + 1], maxx);
  }
}

inline int main() {
  cin >> n;
  for (int i = 1; i <= n; ++i) cin >> t[i];
  dp = f, DP();
  reverse(t + 1, t + 1 + n);
  dp = g, DP();
  reverse(t + 1, t + 1 + n);
  reverse(g + 1, g + 1 + n);
  for (int i = 1; i <= n; ++i) sum[i] = sum[i - 1] + t[i];
  solve(1, n);
  cin >> m;
  for (int p, x; m; --m) {
    cin >> p >> x;
    cout << max(f[p - 1] + g[p + 1], h[p] + t[p] - x) << '\n';
  }
  return 0;
}

}  // namespace BlueQuantum

int main() {
#ifndef ONLINE_JUDGE
#ifdef LOCAL
  freopen("/tmp/CodeTmp/testdata.in", "r", stdin);
  freopen("/tmp/CodeTmp/testdata.out", "w", stdout);
#else
  freopen("AT2274 [ARC066D] Contest with Drinks Hard.in", "r", stdin);
  freopen("AT2274 [ARC066D] Contest with Drinks Hard.out", "w", stdout);
#endif
#endif

  ios::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
  return BlueQuantum::main();
}
